- polynomial time approximation
- полиномиально-временная аппроксимация, аппроксимация за полиномиальное время
Англо-русский словарь по компьютерной безопасности. Академик.ру. 2011.
polynomial time approximation
Смотреть что такое "polynomial time approximation" в других словарях:
Polynomial-time approximation scheme — In computer science, a polynomial time approximation scheme (abbreviated PTAS) is a type of approximation algorithm for optimization problems (most often, NP hard optimization problems).A PTAS is an algorithm which takes an instance of an… … Wikipedia
Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… … Wikipedia
Approximation algorithm — In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP hard problems; since it is unlikely that there … Wikipedia
Tutte polynomial — This article is about the Tutte polynomial of a graph. For the Tutte polynomial of a matroid, see Matroid. The polynomial x4 + x3 + x2y is the Tutte polynomial of the Bull graph. The red line shows the intersection with the plane … Wikipedia
Chromatic polynomial — All nonisomorphic graphs on 3 vertices and their chromatic polynomials, clockwise from the top. The independent 3 set: k3. An edge and a single vertex: k2(k − 1). The 3 path: k(k − 1)2. The 3 clique … Wikipedia
K-approximation of k-hitting set — In computer science, k approximation of k hitting set is an approximation algorithm for weighted hitting set. The input is a collection S of subsets of some universe T and a mapping W from S to non negative numbers called the weights of the… … Wikipedia
Characteristic polynomial — This article is about the characteristic polynomial of a matrix. For the characteristic polynomial of a matroid, see Matroid. For that of a graded poset, see Graded poset. In linear algebra, one associates a polynomial to every square matrix: its … Wikipedia
PTAS — Polynomial Time Approximation Scheme (Academic & Science » Mathematics) … Abbreviations dictionary
Clique problem — The brute force algorithm finds a 4 clique in this 7 vertex graph (the complement of the 7 vertex path graph) by systematically checking all C(7,4)=35 4 vertex subgraphs for completeness. In computer science, the clique problem refers to any of… … Wikipedia
Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… … Wikipedia
Maximum cut — A maximum cut. For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the max cut problem. The problem can be stated simply as follows. One wants a subset… … Wikipedia
